#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>

class Solution {
public:

    int temp[50001];
    void Mergesort(vector<int>& nums, int left, int right, int& ret)
    {
        if (left >= right) return;
        int mid = (left + right) / 2;
        Mergesort(nums, left, mid, ret);
        Mergesort(nums, mid + 1, right, ret);

        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int cur = left;
        while (begin1 <= end1 && begin2 <= end2)
        {
            if (nums[begin1] < nums[begin2])
            {
                temp[cur++] = nums[begin2++];
            }
            else
            {
                int r = begin2;
                while (r <= end2)
                {
                    if (nums[begin1] / 2.0 > nums[r] || (nums[begin1] / 2.0 == nums[r]) && (nums[begin1] % 2 == 1))
                    {
                        ret += end2 - r + 1;//2*3=6;
                        break;
                    }
                    r++;
                }
                temp[cur++] = nums[begin1++];
            }
        }
        while (begin1 <= end1)
        {
            temp[cur++] = nums[begin1++];
        }
        while (begin2 <= end2)
        {
            temp[cur++] = nums[begin2++];
        }
        for (int i = left; i <= right; i++)
        {
            nums[i] = temp[i];
        }
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        int ret = 0;
        Mergesort(nums, 0, n - 1, ret);
        return ret;
    }
};

